home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1997 January: Mac OS SDK / Dev.CD Jan 97 SDK2.toast / Development Kits (Disc 2) / OpenDoc Development Framework / ODFDev / ODF / Found / FWCollec / SLSrtArr.cpp < prev    next >
Encoding:
Text File  |  1996-09-17  |  8.0 KB  |  300 lines  |  [TEXT/MPS ]
  1. //========================================================================================
  2. //
  3. //    File:                SLSrtArr.cpp
  4. //    Release Version:    $ ODF 2 $
  5. //
  6. //    Copyright:    (c) 1993 - 1996 by Apple Computer, Inc., all rights reserved.
  7. //
  8. //========================================================================================
  9.  
  10. #include "FWFound.hpp"
  11.  
  12. #ifndef SLSRTARR_H
  13. #include "SLSrtArr.h"
  14. #endif
  15.  
  16. #ifndef SLMEMMGR_H
  17. #include "SLMemMgr.h"
  18. #endif
  19.  
  20. #ifndef FWPRIDEB_H
  21. #include "FWPriDeb.h"
  22. #endif
  23.  
  24. #ifdef FW_BUILD_MAC
  25. #pragma segment fwcollec
  26. #endif
  27.  
  28. //========================================================================================
  29. // Local constants
  30. //========================================================================================
  31.  
  32. const long kDefaultCapacity = 16;
  33.  
  34. //========================================================================================
  35. // FW_SPrivSortedArray
  36. //========================================================================================
  37.  
  38. struct FW_SPrivSortedArray
  39. {
  40.     void**    fArray;
  41.     long    fLength;
  42.     long    fCapacity;
  43.     FW_SortedArray_CompareFunction    fCompare;
  44. };
  45.  
  46. //========================================================================================
  47. // Global functions
  48. //========================================================================================
  49.  
  50. //----------------------------------------------------------------------------------------
  51. // FW_PrivSortedArray_New
  52. //----------------------------------------------------------------------------------------
  53.  
  54. FW_HSortedArray FW_PrivSortedArray_New(FW_PlatformError* error, FW_SortedArray_CompareFunction compare)
  55. {
  56.     // No try block necessary - Do not throw
  57.     *error = FW_xNoError;
  58.     FW_HSortedArray self = (FW_HSortedArray) FW_PrimitiveAllocateBlock(sizeof(FW_SPrivSortedArray));
  59.     if (!self)
  60.     {
  61.         *error = FW_xMemoryExhausted;
  62.         return NULL;
  63.     }
  64.     self->fArray = (void**) FW_PrimitiveAllocateBlock(sizeof(void*)*kDefaultCapacity);
  65.     if (!self->fArray)
  66.     {
  67.         *error = FW_xMemoryExhausted;
  68.         return NULL;
  69.     }
  70.     self->fLength = 0;
  71.     self->fCapacity = kDefaultCapacity;
  72.     FW_ASSERT(compare != 0);
  73.     self->fCompare = compare;
  74.     
  75.     return self;
  76. }
  77.  
  78. //----------------------------------------------------------------------------------------
  79. // FW_PrivSortedArray_Dispose
  80. //----------------------------------------------------------------------------------------
  81.  
  82. void    FW_PrivSortedArray_Dispose(FW_HSortedArray self)
  83. {
  84.     // No try block necessary - Do not throw
  85.     FW_PrimitiveFreeBlock(self->fArray);
  86.     FW_PrimitiveFreeBlock(self);
  87. }
  88.  
  89. //----------------------------------------------------------------------------------------
  90. // FW_PrivSortedArray_GetLength
  91. //----------------------------------------------------------------------------------------
  92.  
  93. long FW_PrivSortedArray_GetLength(FW_HSortedArray self)
  94. {
  95.     // No try block necessary - Do not throw
  96.     return self->fLength;
  97. }
  98.  
  99. //----------------------------------------------------------------------------------------
  100. // FW_PrivSortedArray_Get
  101. //----------------------------------------------------------------------------------------
  102.  
  103. void* FW_PrivSortedArray_GetItemAt(FW_HSortedArray self, long index)
  104. {
  105.     // No try block necessary - Do not throw
  106.     FW_ASSERT(index <= self->fLength);
  107.     return self->fArray[index];
  108. }
  109.  
  110. //----------------------------------------------------------------------------------------
  111. // FW_PrivSortedArray_Find
  112. //----------------------------------------------------------------------------------------
  113.  
  114. FW_Boolean FW_PrivSortedArray_Find(FW_HSortedArray self, 
  115.                             void* item,
  116.                             long* index)
  117. {
  118.     // No try block necessary - Do not throw
  119.     FW_ASSERT(self->fLength >= 0);
  120.     FW_ASSERT(self->fCapacity >= self->fLength);
  121.  
  122.     *index = 0;
  123.     if (self->fLength == 0)
  124.         return false;
  125.  
  126.     long lo = 0;
  127.     int result = (*self->fCompare)(item, self->fArray[lo]);
  128.     if (result < 0)
  129.         return false;
  130.     if (result == 0)
  131.         return true;
  132.  
  133.     long high = self->fLength - 1;
  134.     *index = high;
  135.     result = (*self->fCompare)(item, self->fArray[high]);
  136.     if (result == 0)
  137.         return true;
  138.     if (result > 0)
  139.     {
  140.         *index = high+1;
  141.         return false;
  142.     }
  143.     
  144.     FW_ASSERT(lo < high);
  145.     FW_ASSERT((*self->fCompare)(item, self->fArray[lo]) > 0);
  146.     FW_ASSERT((*self->fCompare)(item, self->fArray[high]) < 0);
  147.  
  148.     while (lo+1 < high)
  149.     {
  150.         long mid = (lo+high)/2;
  151.         result = (*self->fCompare)(item, self->fArray[mid]);
  152.         if (result == 0)
  153.         {
  154.             *index = mid;
  155.             return true;
  156.         }
  157.         if (result < 0)
  158.         {
  159.             high = mid;
  160.         }
  161.         else
  162.         {
  163.             lo = mid;
  164.         }
  165.  
  166.         FW_ASSERT((*self->fCompare)(item, self->fArray[lo]) > 0);
  167.         FW_ASSERT((*self->fCompare)(item, self->fArray[high]) < 0);
  168.     }
  169.     
  170.     // FW_ASSERT((*self->fCompare)(item, self->fArray[lo]) > 0);
  171.     // FW_ASSERT((*self->fCompare)(item, self->fArray[lo+1]) < 0);
  172.     
  173.     *index = lo+1;
  174.     return false;
  175. }
  176.  
  177. //----------------------------------------------------------------------------------------
  178. // Grow
  179. //----------------------------------------------------------------------------------------
  180.  
  181. static void Grow(FW_HSortedArray self, 
  182.                 FW_PlatformError* error)
  183. {
  184.     // No try block necessary - Do not throw
  185.     *error = 0;
  186.     long newCapacity = self->fCapacity*2;
  187.     self->fArray = (void**) FW_PrimitiveResizeBlock(self->fArray, 
  188.                                                     sizeof(void*)*newCapacity);
  189.     if (self->fArray == 0)
  190.     {
  191.         *error = FW_xMemoryExhausted;
  192.         return;
  193.     }
  194.     self->fCapacity = newCapacity;
  195. }
  196.  
  197. //----------------------------------------------------------------------------------------
  198. // FW_PrivSortedArray_Insert
  199. //----------------------------------------------------------------------------------------
  200.  
  201. void FW_PrivSortedArray_Insert(FW_HSortedArray self, 
  202.                             void* newItem,
  203.                             long index,
  204.                             FW_PlatformError* error)
  205. {
  206.     // No try block necessary - Do not throw
  207.     *error = FW_xNoError;
  208.     FW_ASSERT(self->fLength >= 0);
  209.     FW_ASSERT(self->fCapacity >= self->fLength);
  210.     FW_ASSERT(index >= 0);
  211.     FW_ASSERT(index <= self->fLength);
  212.     
  213.     FW_ASSERT((index==self->fLength) || ((*self->fCompare)(newItem, self->fArray[index]) < 0));
  214.     FW_ASSERT((index==0) || ((*self->fCompare)(newItem, self->fArray[index-1]) > 0));
  215.  
  216.     if (self->fLength == self->fCapacity)
  217.     {
  218.         Grow(self, error);
  219.         if (*error != FW_xNoError)
  220.             return;
  221.     }
  222.     
  223.     FW_PrimitiveCopyMemory(self->fArray + index,
  224.                         self->fArray + index + 1,
  225.                         (self->fLength - index) * sizeof(void*));
  226.     
  227.     self->fArray[index] = newItem;
  228.     ++self->fLength;
  229. }
  230.  
  231. //----------------------------------------------------------------------------------------
  232. // FW_PrivSortedArray_Add
  233. //----------------------------------------------------------------------------------------
  234.  
  235. void FW_PrivSortedArray_Add(FW_HSortedArray self, 
  236.                             void* newItem,
  237.                             long* index,
  238.                             FW_PlatformError* error)
  239. {
  240.     // No try block necessary - Do not throw
  241.     *error = FW_xNoError;
  242.     FW_Boolean result = FW_PrivSortedArray_Find(self, newItem, index);
  243.     FW_ASSERT(!result);
  244.     if (result)
  245.     {
  246.         *error = FW_xBadInsert;
  247.         return;
  248.     }
  249.     FW_PrivSortedArray_Insert(self, newItem, *index, error);
  250.     return;
  251. }
  252.  
  253. //----------------------------------------------------------------------------------------
  254. // FW_PrivSortedArray_RemoveIndex
  255. //----------------------------------------------------------------------------------------
  256.  
  257. void FW_PrivSortedArray_RemoveIndex(FW_HSortedArray self,
  258.                                     long index,
  259.                                     FW_PlatformError* error)
  260. {
  261.     // No try block necessary - Do not throw
  262.     *error = FW_xNoError;
  263.     if (index > (self->fLength - 1))
  264.     {
  265.         *error = FW_xBadRemove;
  266.         return;
  267.     }
  268.     
  269.     --self->fLength;
  270.     
  271.     if (index < self->fLength)
  272.     {
  273.         FW_PrimitiveCopyMemory(self->fArray + index + 1,
  274.                             self->fArray + index,
  275.                             (self->fLength - index) * sizeof(void*));
  276.                             
  277.     }
  278.     return;
  279. }
  280.  
  281. //----------------------------------------------------------------------------------------
  282. // FW_PrivSortedArray_RemoveItem
  283. //----------------------------------------------------------------------------------------
  284.  
  285. void FW_PrivSortedArray_RemoveItem(FW_HSortedArray self,
  286.                                 void* item,
  287.                                 FW_PlatformError* error)
  288. {
  289.     *error = FW_xNoError;
  290.     long index;
  291.     FW_Boolean result = FW_PrivSortedArray_Find(self, item, &index);
  292.     FW_ASSERT(result);
  293.     if (!result)
  294.     {
  295.         *error = FW_xBadRemove;
  296.         return;
  297.     }
  298.     FW_PrivSortedArray_RemoveIndex(self, index, error);
  299.     return;
  300. }